package com.hc.programming.tree;

import java.util.Arrays;

/**
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 * <p>
 * 示例 1：
 * 输入：root = [1,2,3,4,5,6]
 * 输出：6
 * 示例 2：
 * 输入：root = []
 * 输出：0
 * 示例 3：
 * 输入：root = [1]
 * 输出：1
 * <p>
 * 提示：
 * 树中节点的数目范围是[0, 5 * 10^4]
 * 0 <= Node.val <= 5 * 10^4
 * 题目数据保证输入的树是 完全二叉树
 * <p>
 * 进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/14 14:26
 */
public class 完全二叉树的节点个数 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{3, 9, 20, null, null, 15, 7};
        TreeNode tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=5,--" + countNodes(tree));
        arr = new Integer[]{1, null, 2};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=2,--" + countNodes(tree));
        arr = new Integer[]{2, null, 3, null, 4, null, 5, null, 6};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=5,--" + countNodes(tree));
        arr = new Integer[]{1, 2, 3, 4, 5, 6, 7};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=7,--" + countNodes(tree));
    }

    /**
     * 先两边，再中间
     *
     * @param root
     * @return
     */
    public static int countNodes(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (root.left == null) return 1 + countNodes(root.right);
        if (root.right == null) return 1 + countNodes(root.left);
        int leftHeight = getLeftHigh(root.left);
        int rightHeight = getRightHigh(root.right);
        if (leftHeight == rightHeight) return (1 << (leftHeight + 1)) - 1;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    private static int getRightHigh(TreeNode right) {
        if (right == null) return 0;
        return 1 + getRightHigh(right.right);
    }

    private static int getLeftHigh(TreeNode left) {
        if (left == null) return 0;
        return 1 + getLeftHigh(left.left);
    }

}
